<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>数据结构之图</title>
  </head>
  <body>
    <script type="text/javascript">
      var Queue = function () {
        var items = [];
        //入队
        this.enqueue = function (element) {
          items.push(element);
        };
        // 出队
        this.dequeue = function () {
          return items.shift();
        };
        //查看队列头
        this.front = function () {
          return items[0];
        };
        //检查队列是否为空
        this.isEmpty = function () {
          return items.length === 0;
        };
        //队列大小
        this.size = function () {
          return items.length;
        };
      };
      /*
       * 图
       * 1、可用于实现地图、社交网络等
       * 2、有向图和无向图
       * 3、表示图结构的方式：邻接矩阵、邻接表
       * 4、图遍历：广度优先和深度优先
       * 5、每个节点有三种状态：未发现、已发现、已探索
       */
      var Graph = function () {
        var vertices = []; // 图的顶点，以数组形式存储每个顶点
        var edges = {}; // 图的边，以对象形式存储每个顶点包含的边

        // 添加顶点
        this.addVertex = function (v) {
          vertices.push(v);
          edges[v] = [];
        };

        // 添加边
        this.addEdge = function (a, b) {
          edges[a].push(b);
          edges[b].push(a);
          console.log(edges);
        };

        // 打印图的邻接表
        this.print = function () {
          var str = "";
          for (var i = 0; i < vertices.length; i++) {
            var vertice = vertices[i];
            str += vertice + " => ";
            var edge = edges[vertice];
            for (var j = 0; j < edge.length; j++) {
              str += edge[j] + " ";
            }
            str += "\n";
          }
          console.log(str);
        };

        // 广度优先遍历，white为未发现，grey为已发现，black为已探索
        var initColor = function () {
          // 将所有顶点的颜色置为白色，表示未发现
          var color = {};
          for (var i = 0; i < vertices.length; i++) {
            color[vertices[i]] = "white";
          }
          return color;
        };
        this.bfs = function (v, callback) {
          var color = initColor();
          var queue = new Queue();
          queue.enqueue(v);
          while (!queue.isEmpty()) {
            var currVertice = queue.dequeue(); // 顶点出列
            var currEdge = edges[currVertice]; // 存储该顶点相关的边
            for (var i = 0; i < currEdge.length; i++) {
              // 遍历该顶点相关的所有边
              var nextVertice = currEdge[i]; // 与该顶点相连的其他所有顶点
              if (color[nextVertice] == "white") {
                // 未发现的顶点全部入列，并标识为已发现
                queue.enqueue(nextVertice);
                color[nextVertice] = "grey";
              }
            }
            color[currVertice] = "black"; // 遍历结束后将该顶点标识为已探索
            if (callback) {
              // 回调函数
              callback(currVertice);
            }
          }
        };

        // 带最短路径的广度优先算法
        this.BFS = function (v, callback) {
          var color = initColor();
          var queue = new Queue();
          var distance = {}; // 存储某个顶点到其它顶点的距离
          var backPoint = {}; // 存储某个顶点的回溯点
          for (var i = 0; i < vertices.length; i++) {
            distance[vertices[i]] = 0;
            backPoint[vertices[i]] = null;
          }
          queue.enqueue(v);
          while (!queue.isEmpty()) {
            var currVertice = queue.dequeue(); // 顶点出列
            var currEdge = edges[currVertice]; // 存储该顶点相关的边
            for (var i = 0; i < currEdge.length; i++) {
              // 遍历该顶点相关的所有边
              var nextVertice = currEdge[i]; // 与该顶点相连的其他所有顶点
              if (color[nextVertice] == "white") {
                // 未发现的顶点全部入列，并标识为已发现
                queue.enqueue(nextVertice);
                color[nextVertice] = "grey";
                backPoint[nextVertice] = currVertice; // 设置回溯点
                distance[nextVertice] = distance[currVertice] + 1; // 设置距离
              }
            }
            color[currVertice] = "black"; // 遍历结束后将该顶点标识为已探索
            if (callback) {
              // 回调函数
              callback(currVertice);
            }
          }
          return {
            backPoint: backPoint,
            distance: distance,
          };
        };

        // 深度优先算法
        var dfs = function (u, color, callback) {
          color[u] = "grey";
          var n = edges[u];
          for (var i = 0; i < n.length; i++) {
            var w = n[i];
            if (color[w] == "white") {
              dfs(w, color, callback);
            }
          }
          color[u] = "black";
          if (callback) {
            callback(u);
          }
        };
        this.DFS = function (v, callback) {
          var color = initColor();
          dfs(v, color, callback);
        };
      };
      var g = new Graph();
      g.addVertex("A");
      g.addVertex("B");
      g.addVertex("C");
      g.addVertex("D");
      g.addVertex("E");
      g.addVertex("F");
      g.addEdge("A", "B");
      g.addEdge("A", "C");
      g.addEdge("A", "D");
      g.addEdge("C", "D");
      g.addEdge("B", "E");
      g.addEdge("F", "B");
      g.print();

      var Stack = function () {
        var items = []; //私有

        // push 栈顶添加元素
        this.push = function (element) {
          items.push(element);
        };
        // pop 移除栈顶元素
        this.pop = function () {
          return items.pop();
        };
        // peek 检查栈顶
        this.peek = function () {
          return items[items.length - 1];
        };

        // 检查栈 是否为空
        this.isEmpty = function () {
          return items.length == 0;
        };

        // 清除栈
        this.clear = function () {
          items = [];
        };

        // 获取栈的大小
        this.size = function () {
          return items.length;
        };

        // 检查items
        this.getItems = function () {
          return items;
        };
      };

      // 实现最短路径算法：从当前点出发，寻找回溯点。广度优先算法保证了每个顶点的回溯点是最近的。
      var paths = g.BFS("A");
      var ShortestPath = function (from, to) {
        var currVertice = to;
        var path = new Stack();
        while (currVertice != from) {
          path.push(currVertice);
          currVertice = paths.backPoint[currVertice];
        }
        path.push(currVertice);
        var str = "";
        while (!path.isEmpty()) {
          str += path.pop() + "-";
        }
        str = str.slice(0, str.length - 1);
        console.log(from + "到" + to + "的最短路径为：" + str);
      };
      ShortestPath("A", "F");
    </script>
  </body>
</html>
